#pragma once
#include<iostream>
using namespace std;

template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if(cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Insert(const K& key)
	{
		//树为空，直接新增节点，赋值给root指针
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到这个值,返回false，二叉搜索树不能存相同的值
				return false;
			}
		}
		//找到位置，插入新节点
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到节点，进行删除
				//情况一：要删除的节点有 0或1 个孩子
				if (cur->_left == nullptr)//被删除节点的左为空
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)//被删除节点的右为空
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}	
					delete cur;
					return true;
				}
				else
				{
					//情况二：被删除的节点有 2个孩子
					//办法一：找被删除节点的左子树的最大节点来代替
					//办法二：找被删除节点的右子树的最小节点来代替
					//这里采用办法二
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;
					}
					//此时找到了右子树的最小值,此节点的值与要被删除节点的值进行交换
					cur->_key = rightMin->_key;

					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;//使该节点的前一个节点与该节点的右进行连接
					else
						rightMinP->_right = rightMin->_right;

					delete rightMin;;
					return true;
				}
			}
		}
		//没有找到这个节点
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};